package com.company.algo.DP.palindromic;

/**516. 最长回文子序列
 给定一个字符串，计算这个字符串中最长的回文子序列，返回该序列的长度
 【子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。】
 动态规划：
 dp[i][j]：s[i:j]范围内最长的回文子【序列】长度
 dp[i][j] =
    1. s[i]==s[j], dp[i+1][j-1]+2
    2. s[i]!=s[j], max(dp[i+1][j],dp[i][j-1])
 遍历顺序：
   dp[i][j] <- dp[i+1][j-1]，所以依旧为i逆序,j正序
 初始化：从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i和j相同时候的情况
 所以需要⼿动初始化⼀下，当i与j相同，那么dp[i][j]⼀定是等于1的
 */
public class LongestPalindromeSubseq {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) dp[i][i] = 1;
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i+1; j < s.length() ; j++) {
                if (s.charAt(i)==s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }
        return dp[0][s.length()-1];
    }

}
